package datastruct.lineList;

/**
 * 链表
 *
 * @author RunningShrimp
 * @date 2021/5/8  23:28
 */
public class LinkList<E> implements LineList<E> {
    /**
     * 链表长度
     */
    private int size;
    /**
     * 头节点
     */
    private Node head;

    public LinkList() {
        this.size = 0;
        this.head = new Node();

    }

    @Override
    public boolean add(E e, int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("索引无效");
        }
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        node.next = new Node(e, node.next);
        size++;
        return true;
    }

    @Override
    public boolean add(E e) {
        return add(e, 0);
    }

    public boolean addLast(E e) {
        return add(e, size);
    }

    @Override
    public E remove(E e) {
        if (!contains(e)) {
            throw new IllegalStateException("链表不包含元素");
        }
        Node node = head.next;
        while (node != null) {
            if (node.date.equals(e)) {
                node.next = node.next.next;
                size--;
            }
            node = node.next;
        }
        return e;
    }

    public E removeFirst() {
        Node first = head.next;
        E e = first.date;
        head.next = first.next;
        first.next = null;
        return e;
    }

    public E removeLast() {
        return remove(size - 1);
    }

    @Override
    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("索引无效");
        }
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        node.next = node.next.next;
        size--;
        return node.date;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("索引无效");
        }
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.date;
    }

    public E getLast() {
        return get(size);
    }

    public E getFirst() {
        return get(0);
    }

    @Override
    public boolean set(E e, int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("索引无效");
        }
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        node.date = e;
        return true;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(E e) {
        Node node = head.next;
        while (node != null) {
            if (node.date.equals(e)) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    @Override
    public int find(E e) {
        Node node = head.next;
        for (int i = 0; i < size; i++) {
            if (node.date.equals(e)) {
                return i;
            }
            node = node.next;
        }
        return -1;
    }

    @Override
    public boolean clear() {
        size = 0;
        head.next = null;
        return true;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("LinkList's size is ").append(size).append(", element is {");
        Node node = head.next;
        while (node != null) {
            sb.append(node.date);
            node = node.next;
            if (node != null) {
                sb.append(" , ");
            }
        }
        sb.append("}");
        return sb.toString();
    }

    /**
     * 节点，双向链表
     */
    private class Node {
        public E date;
        public Node next;

        public Node(E e, Node next) {
            this.date = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null);
        }

        @Override
        public String toString() {
            return date.toString();
        }
    }
}
